#include <iostream>
#include <unordered_map>
using namespace std;
// Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
//快慢指针
    //通过相遇点求入环点方法的数学推理:
    //入环点前长度(节点个数) x 环长 k meet点到入环点y
    //相遇时s指针走了x+y(一圈之内必定能追上) f走了x+(x/k*k)[入环前可能就一直在转圈除法向下取整]+y
    // x+(x/k*k)+y=2x+2y[f走了二倍s走的距离]
    // ==>x=(x/k*k)-y
    // 入环点到meet点=y
    // 所以 head到入环点的距离 = x = (x/k*k)-y= 从meet开始走x/k*k圈后回退y(回退到入环点)
class Solution {
public:
    //求相遇点 有环一定相遇,因为距离每次-1
    ListNode* cycle_meet(ListNode*head){
        ListNode*fast,*slow;
        fast=slow=head;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow)return fast;
        }
        return nullptr;
    }
    //求入环点 
    ListNode* cycle_start(ListNode* head,ListNode*meet){
        while(meet){
            if(head==meet)break;
            head=head->next;
            meet=meet->next;
        }
        return meet;
    }
    ListNode *detectCycle(ListNode *head) {
        return cycle_start(head,cycle_meet(head));
    }
};
//空间换时间
class Solution
{
public:
    ListNode *detectCycle(ListNode *head)
    {
        unordered_map<ListNode *, size_t> u_map;
        while (head && head->next)
        {
            if (++u_map[head] == 2)
                return head;
            head = head->next;
        }
        return nullptr;
    }
};